{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Difficulty of a Job Schedule"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDifficulty"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #工作计划的最低难度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你需要制定一份&nbsp;<code>d</code>&nbsp;天的工作计划表。工作之间存在依赖，要想执行第&nbsp;<code>i</code>&nbsp;项工作，你必须完成全部&nbsp;<code>j</code>&nbsp;项工作（&nbsp;<code>0 &lt;= j &lt; i</code>）。</p>\n",
    "\n",
    "<p>你每天 <strong>至少</strong>&nbsp;需要完成一项任务。工作计划的总难度是这&nbsp;<code>d</code>&nbsp;天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。</p>\n",
    "\n",
    "<p>给你一个整数数组&nbsp;<code>jobDifficulty</code>&nbsp;和一个整数&nbsp;<code>d</code>，分别代表工作难度和需要计划的天数。第&nbsp;<code>i</code>&nbsp;项工作的难度是&nbsp;<code>jobDifficulty[i]</code>。</p>\n",
    "\n",
    "<p>返回整个工作计划的 <strong>最小难度</strong> 。如果无法制定工作计划，则返回&nbsp;<strong>-1&nbsp;</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/26/untitled.png\" style=\"height: 304px; width: 365px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>jobDifficulty = [6,5,4,3,2,1], d = 2\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>第一天，您可以完成前 5 项工作，总难度 = 6.\n",
    "第二天，您可以完成最后一项工作，总难度 = 1.\n",
    "计划表的难度 = 6 + 1 = 7 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>jobDifficulty = [9,9,9], d = 4\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>就算你每天完成一项工作，仍然有一天是空闲的，你无法制定一份能够满足既定工作时间的计划表。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>jobDifficulty = [1,1,1], d = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>工作计划为每天一项工作，总难度为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>jobDifficulty = [7,1,7,1,7,1], d = 3\n",
    "<strong>输出：</strong>15\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>jobDifficulty = [11,111,22,222,33,333,44,444], d = 6\n",
    "<strong>输出：</strong>843\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= jobDifficulty.length &lt;= 300</code></li>\n",
    "\t<li><code>0 &lt;=&nbsp;jobDifficulty[i] &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= d &lt;= 10</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-difficulty-of-a-job-schedule](https://leetcode.cn/problems/minimum-difficulty-of-a-job-schedule/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-difficulty-of-a-job-schedule](https://leetcode.cn/problems/minimum-difficulty-of-a-job-schedule/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,5,4,3,2,1]\\n2', '[9,9,9]\\n4', '[1,1,1]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n = len(jobDifficulty)\n",
    "        if n < d:\n",
    "            return -1\n",
    "        dp = [[float(\"inf\")] * (d + 1) for _ in range(n)]\n",
    "        \n",
    "        dp[-1][d] = jobDifficulty[-1]\n",
    "        for i in range(n - 2, d - 2, -1):\n",
    "            dp[i][d] = max(jobDifficulty[i], dp[i + 1][d])\n",
    "\n",
    "        for day in range(d - 1, 0, -1):\n",
    "            for i in range(day - 1, n - (d - day)):\n",
    "                hardest = 0\n",
    "                for j in range(i, n - (d - day)):\n",
    "                    hardest = max(hardest, jobDifficulty[j])\n",
    "                    dp[i][day] = min(dp[i][day], hardest + dp[j + 1][day + 1])\n",
    "        \n",
    "        return dp[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        jc = len(jobDifficulty)\n",
    "        if d > jc: return -1\n",
    "        dp = [[1<<32 for i in range(jc+1)] for i in range(d)]\n",
    "        dp[0][0] = jobDifficulty[0]\n",
    "\n",
    "        for i in range(1, jc):\n",
    "            dp[0][i] = max(dp[0][i-1], jobDifficulty[i])\n",
    "        \n",
    "        for i in range(1, d):\n",
    "            for j in range(i, jc):\n",
    "                work = -1 <<32\n",
    "                for k in range(j-1, i-2, -1):\n",
    "                    work = max(jobDifficulty[k+1], work)\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][k] + work)\n",
    "\n",
    "        return dp[d-1][jc-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n = len(jobDifficulty)\n",
    "        if n < d:\n",
    "            return -1\n",
    "        dp = [0] * n\n",
    "        maxv = 0\n",
    "        for i in range(n):\n",
    "            maxv = max(maxv, jobDifficulty[i])\n",
    "            dp[i] = maxv\n",
    "        for i in range(1, d):\n",
    "            for j in range(n-1,i-1,-1):\n",
    "                prev = 0\n",
    "                dp[j] = float('inf')\n",
    "                for k in range(j-1, i-2, -1):\n",
    "                    prev = max(prev, jobDifficulty[k+1])\n",
    "                    dp[j] = min(dp[j], dp[k]+prev)\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty, d) -> int:\n",
    "        if len(jobDifficulty) < d:\n",
    "            return -1\n",
    "        if len(jobDifficulty) == d:\n",
    "            return sum(jobDifficulty)\n",
    "        dp = [[0 for i in range(len(jobDifficulty))] for _ in range(d)]\n",
    "        dp[0] = [max(jobDifficulty[:i]) for i in range(1,len(jobDifficulty))]\n",
    "        for i in range(1,d):\n",
    "            for j in range(len(jobDifficulty)):\n",
    "                min_ = float('inf')\n",
    "                for m in range(j):\n",
    "                    tmp = dp[i-1][m] + max(jobDifficulty[m+1:j+1])\n",
    "                    if tmp < min_:\n",
    "                        min_ = tmp\n",
    "                    \n",
    "                dp[i][j] = min_\n",
    "        \n",
    "        return dp[-1][-1]\n",
    "        \n",
    "\n",
    "            \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n=len(jobDifficulty)\n",
    "        if n<d:\n",
    "            return -1\n",
    "        dp=[[-1]*(n+1) for i in range(d+1)]\n",
    "        dp[1][1]=jobDifficulty[0]\n",
    "        #第一天完成1个,2个,3个 ....n个工作量的最大难度\n",
    "        for i in range(2,n+1):\n",
    "            dp[1][i]=max(dp[1][i-1],jobDifficulty[i-1])\n",
    "        #i-1天完成k个任务,第i天完成k到j之间的任务,work是k到j之间任务的最大难度\n",
    "        for i in range(2,d+1):\n",
    "            for j in range(i,n+1):\n",
    "                dp[i][j]=dp[i-1][j-1]+jobDifficulty[j-1]\n",
    "                work=jobDifficulty[j-1]\n",
    "                for k in range(j-2,i-2,-1):\n",
    "                    work=max(work,jobDifficulty[k])\n",
    "                    \n",
    "                    dp[i][j] = min(dp[i-1][k] + work,dp[i][j])\n",
    "        return dp[d][n]\n",
    "\n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n = len(jobDifficulty)\n",
    "        if n < d:\n",
    "            return -1\n",
    "        dp = [[float('inf') for _ in range(n+1)] for _ in range(d+1)]\n",
    "        dp[1][1]=jobDifficulty[0]\n",
    "        for i in range(2,n+1):\n",
    "            dp[1][i]=max(dp[1][i-1],jobDifficulty[i-1])\n",
    "        for i in range(2,d+1):\n",
    "            for j in range(i,n+1):\n",
    "                for k in range(j):\n",
    "                    dp[i][j]=min(dp[i][j],dp[i-1][k]+max(jobDifficulty[k:j]+[0]))\n",
    "                 #   print(i,j,dp[i])\n",
    "        return dp[d][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# dp[i][j]表示前i天完成前j项任务所需的最小难度,i、j都是从0开始数。\n",
    "# dp[1][1] = jd[0:]\n",
    "# dp[1][2] = min(jd[0:1])\n",
    "# dp[1][3] = min(jd[:2])\n",
    "#\n",
    "# dp[2][1] = min(dp[1][1], dp[1][2], ...)\n",
    "# dp[2][j] = min(dp[i-1][j-1] + jd[j-1+1:j],  dp[i-1][j-2] + jd[j-2+1:j],..., dp[i-1][0] + jd[0+1:j])\n",
    "class Solution:\n",
    "    def minDifficulty(self, jd: List[int], d: int) -> int:\n",
    "        n = len(jd)\n",
    "        if d > n:\n",
    "            return -1\n",
    "        f = [[999999 for _ in range(n + 1)] for _ in range(d + 1)] # f[i][j] i天前完成j项任务所需最小难度\n",
    "        mx = [[0 for _ in range(n + 1)] for _ in range(n + 1)]    # mx[p][q] p:q之间jd最大值\n",
    "\n",
    "        for p in range(1, n+1):\n",
    "            for q in range(1, n+1):\n",
    "                \n",
    "                if p == q:\n",
    "                    mx[p][q] = jd[p-1]\n",
    "                else:\n",
    "                    # mx[p][q] = max(jd[p-1:q-1])\n",
    "                    mx[p][q] = max(mx[p][q-1], jd[q-1])\n",
    "        \n",
    "        # f[i][j] = max(f[i][k], mx[i][k:j])\n",
    "        for i in range(1, d+1):\n",
    "            for j in range(1, n+1):\n",
    "                if i == 1:\n",
    "                    f[1][j] = mx[1][j]\n",
    "                else:\n",
    "                    for k in range(1, j):\n",
    "                        f[i][j] = min(f[i][j], f[i-1][k]+mx[k+1][j])\n",
    "        return f[d][n]\n",
    "            \n",
    "        # int n = jd.size();\n",
    "        # if (d > n) return -1;\n",
    "        # int f[n + 1][d + 1];\n",
    "        # int mx[n + 1][n + 1];\n",
    "        # memset(mx, 0, sizeof mx);\n",
    "        # memset(f, 0x3f, sizeof f);\n",
    "        # for (int i = 1; i <= n; i ++)\n",
    "        #     for (int j = i; j <= n; j ++) {\n",
    "        #         if (j == i) mx[i][j] = jd[i - 1];\n",
    "        #         else {\n",
    "        #             mx[i][j] = max(mx[i][j - 1], jd[j - 1]);\n",
    "        #         }\n",
    "        #     }\n",
    "        # for (int i = 1; i <= d; i ++) \n",
    "        #     for (int j = 1; j <= n; j ++) {\n",
    "        #         if (i == 1) f[j][i] = mx[1][j];\n",
    "        #         else {\n",
    "        #             for (int k = 1; k < j ; k ++) \n",
    "        #                 f[j][i] = min(f[j][i], f[k][i - 1] + mx[k + 1][j]);\n",
    "        #         }\n",
    "        #     }\n",
    "        # return f[n][d];\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, d):\n",
    "            if len(jobDifficulty)-idx < d:\n",
    "                return inf\n",
    "            if len(jobDifficulty)-idx == d:\n",
    "                return sum(jobDifficulty[idx:])\n",
    "            if d == 1:\n",
    "                return max(jobDifficulty[idx:])\n",
    "            res, mx = inf, 0\n",
    "            for i in range(idx+1, len(jobDifficulty)+1):\n",
    "                mx = max(mx, jobDifficulty[i-1])\n",
    "                res = min(res, dfs(i, d-1) + mx)\n",
    "            return res\n",
    "\n",
    "\n",
    "        if len(jobDifficulty) < d:\n",
    "            return -1\n",
    "        return dfs(0, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        if d > len(jobDifficulty):\n",
    "            return -1\n",
    "        if d == 1:\n",
    "            return max(jobDifficulty)\n",
    "        max_num = sys.maxsize\n",
    "        size = len(jobDifficulty)\n",
    "        arr = [[-1 for _ in range(size)] for _ in range(d+1)]\n",
    "\n",
    "        max_diff = -1\n",
    "        for i in range(size-(d-1)):\n",
    "            max_diff = max(jobDifficulty[i], max_diff)\n",
    "            arr[0][i] = max_diff\n",
    "\n",
    "        for i in range(1, d):\n",
    "            max_diff = -1\n",
    "            for j in range(size-(d-1-i)-1, i-1, -1):\n",
    "                if i == d-1:\n",
    "                    max_diff = max(max_diff, jobDifficulty[j])\n",
    "                    arr[i][j] = arr[i-1][j-1] + max_diff\n",
    "                else:\n",
    "                    arr[i][j] = max_num\n",
    "                    max_diff = -1\n",
    "                    for k in range(j, i-1, -1):\n",
    "                        max_diff = max(max_diff, jobDifficulty[k])\n",
    "                        arr[i][j] = min(arr[i][j], arr[i - 1][k - 1] + max_diff)\n",
    "        return min(arr[d-1][d-1:])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n = len(jobDifficulty)\n",
    "        if n < d:\n",
    "            return -1\n",
    "        dp = [[float(\"inf\")] * n for _ in range(d+1)]\n",
    "        local_max = 0\n",
    "        for j in range(n):\n",
    "            local_max = max(local_max, jobDifficulty[j])\n",
    "            dp[1][j] = local_max\n",
    "        for i in range(2, d+1):\n",
    "            for j in range(i-1, n):\n",
    "                local_max = 0\n",
    "                for l in range(j-i+2):\n",
    "                    local_max = max(local_max, jobDifficulty[j-l])\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][j-l-1] + local_max)\n",
    "        return int(dp[d][n-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jd: List[int], d: int) -> int: \n",
    "        n = len(jd)\n",
    "        if n < d: return -1\n",
    "        f = [[inf] *(d + 1) for _ in range(n + 1)] \n",
    "        f[0][0] = 0\n",
    "        for i in range(1, n + 1): \n",
    "            for j in range(1, d + 1):\n",
    "                if j > i: continue\n",
    "                maxv = jd[i - 1]\n",
    "                for k in range(i, 0, -1):\n",
    "                    if j > k: continue\n",
    "                    maxv = max(maxv, jd[k - 1])\n",
    "                    f[i][j] = min(f[i][j], f[k - 1][j - 1] + maxv) \n",
    "        return f[n][d]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, job: List[int], d: int) -> int:\n",
    "        n = len(job)\n",
    "        if n <= d: return -1 if n < d else sum(job)\n",
    "        g = [[-1] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                g[i][j] = max(g[i][j - 1], job[j])\n",
    "\n",
    "        f = [[float('inf')] * (d + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, min(i + 1, d + 1)):\n",
    "                for k in range(1, i - j + 2):\n",
    "                    f[i][j] = min(f[i][j], f[i - k][j - 1] + g[i - k][i - 1])\n",
    "        return f[n][d]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        # 动态递归\n",
    "        # 缩小问题规模\n",
    "        n = len(jobDifficulty)\n",
    "        if n < d:\n",
    "            return -1\n",
    "        f = list(accumulate(jobDifficulty, max))\n",
    "\n",
    "        for i in range(1, d):\n",
    "            for j in range(n - 1, i - 1, -1):\n",
    "                f[j] = inf\n",
    "                mx = 0\n",
    "                for k in range(j, i - 1, -1):\n",
    "                    mx = max(mx, jobDifficulty[k])\n",
    "                    f[j] = min(f[j], f[k - 1] + mx)\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        outwork = len(jobDifficulty) - d\n",
    "        if outwork < 0:\n",
    "            return -1\n",
    "        if outwork == 0:\n",
    "            return sum(jobDifficulty)\n",
    "        difs = sum(jobDifficulty)\n",
    "        jobs = [[inf]*len(jobDifficulty) for _ in range(d)]\n",
    "\n",
    "        jobs[0][0] = jobDifficulty[0]\n",
    "        for i in range(1, len(jobDifficulty)):\n",
    "            jobs[0][i] = max(jobs[0][i-1], jobDifficulty[i])\n",
    "        \n",
    "        for i in range(1, d):\n",
    "            jobs[i][i] = sum(jobDifficulty[:i+1])\n",
    "            for j in range(i+1,len(jobDifficulty)):\n",
    "                #jobs[i][j] = jobs[i-1][j-1]+jobDifficulty[j]\n",
    "                for k in range(i-1, j):\n",
    "                    jobs[i][j] = min(jobs[i][j], jobs[i-1][k]+max(jobDifficulty[k+1:j+1]))\n",
    "        \n",
    "\n",
    "        return jobs[d-1][len(jobDifficulty)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        # o（n**2*d）\n",
    "        # dp\n",
    "        n=len(jobDifficulty)\n",
    "        if n<d:return -1\n",
    "        dp=[[inf for _ in range(d+1)]for _ in range(n+1)]\n",
    "        dp[0][0]=0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, d + 1):\n",
    "                mx=0\n",
    "                for k in range(i,0,-1):\n",
    "                    mx=max(mx,jobDifficulty[k-1])\n",
    "                    dp[i][j]=min(dp[i][j],mx+dp[k-1][j-1])\n",
    "        # print(dp)\n",
    "        return dp[n][d]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n=len(jobDifficulty)\n",
    "        if n<d:\n",
    "            return -1\n",
    "        maxls =[ [0 for i in range(n)] for j in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                maxls[i][j]=max(maxls[i][j-1],jobDifficulty[j])\n",
    "        dpls = [[10**9 for i in range(d)] for j in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            dpls[i][0]=maxls[0][i]\n",
    "\n",
    "            for j in range(1,min(d,i+1)):\n",
    "                for m in range(i):\n",
    "                    dpls[i][j]=min(dpls[i][j],dpls[m][j-1]+maxls[m+1][i])\n",
    "        return dpls[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        if d > len(jobDifficulty):\n",
    "            return -1\n",
    "        if d == 1:\n",
    "            return max(jobDifficulty)\n",
    "\n",
    "        dp = [[99999999 for _ in range(d)] for _ in range(len(jobDifficulty))]\n",
    "        pre = [[0 for _ in range(len(jobDifficulty))] for _ in range(len(jobDifficulty))]\n",
    "\n",
    "        for i in range(len(jobDifficulty)):\n",
    "            maxx = jobDifficulty[i]\n",
    "            for j in range(i, len(jobDifficulty)):\n",
    "                maxx = max(maxx, jobDifficulty[j])\n",
    "                pre[i][j] = maxx\n",
    "\n",
    "        for i in range(len(jobDifficulty) - d + 1):\n",
    "            dp[i][0] = pre[0][i]\n",
    "\n",
    "        for i in range(1, len(jobDifficulty)):\n",
    "            for j in range(1, d):\n",
    "                if len(jobDifficulty) - i <  d - j:\n",
    "                    continue\n",
    "                for k in range(j - 1, i):\n",
    "                    dp[i][j] = min(dp[i][j], dp[k][j - 1] + pre[k + 1][i])\n",
    "\n",
    "        return dp[len(jobDifficulty) - 1][d - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDiffculty: List[int], d: int) -> int:\n",
    "        # 数组拆分n个子数组，子数组中最大元素替换整个子数组，返回子数组的最大和\n",
    "\n",
    "        \n",
    "        n = len(jobDiffculty)\n",
    "        if n < d:\n",
    "            return -1\n",
    "        @cache\n",
    "        def dfs(i:int, j:int)-> int: # dfs(i,j)表示用i+1天完成a[0...j]的工作的最大困难度：\n",
    "        \n",
    "            if i == 0: # 只有一天，必须完成所有工作\n",
    "                return max(jobDiffculty[:j + 1])\n",
    "            res, mx = inf, 0\n",
    "            for k in range(j, i - 1, -1):\n",
    "                mx = max(mx, jobDiffculty[k]) # 从a[k]到a[j]的最大值\n",
    "                res = min(res, dfs(i - 1, k - 1) + mx)\n",
    "            return res\n",
    "        return dfs(d - 1, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n = len(jobDifficulty)\n",
    "        if n < d:\n",
    "            return -1\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j==0:\n",
    "                return max(jobDifficulty[:i+1])\n",
    "            max_cur=0\n",
    "            res=inf\n",
    "            for k in range(i,j-1,-1):\n",
    "                max_cur=max(max_cur,jobDifficulty[k])\n",
    "                res=min(res,dfs(k-1,j-1)+max_cur)\n",
    "            return res\n",
    "        res=dfs(len(jobDifficulty)-1,d-1) \n",
    "        return res if res<inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n = len(jobDifficulty)\n",
    "        if n < d:\n",
    "            return -1\n",
    "\n",
    "        @cache\n",
    "        def dfs(start, left):  # 从start项任务开始，剩余d天，最小难度\n",
    "            if n - start < left:\n",
    "                return inf\n",
    "            if left == 0:\n",
    "                if n - start > 0:\n",
    "                    return inf\n",
    "                else:\n",
    "                    return 0\n",
    "            mx = 0\n",
    "            res = inf\n",
    "            for i in range(start, n):\n",
    "                mx = max(mx, jobDifficulty[i])\n",
    "                res = min(res, dfs(i + 1, left - 1) + mx)\n",
    "            # print(start, left, res)\n",
    "            return res\n",
    "        return dfs(0, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        if len(jobDifficulty) < d:\n",
    "            return -1\n",
    "        # 使用dfs来完成\n",
    "        # dfs(i,j)表示还剩余i天时, 完成剩余的jobs[j:]需要的最小代价\n",
    "        n = len(jobDifficulty)\n",
    "\n",
    "        @lru_cache(d * n)\n",
    "        def dfs(days, finished):\n",
    "            if days == 1:\n",
    "                return max(jobDifficulty[finished:])\n",
    "            days -= 1\n",
    "            today_cost = 0\n",
    "            min_cost = float('inf')\n",
    "            for i in range(finished, n - days):\n",
    "                today_cost = max(today_cost, jobDifficulty[i])\n",
    "                min_cost = min(min_cost, today_cost + dfs(days, i + 1))\n",
    "            return min_cost\n",
    "\n",
    "        return dfs(d, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int: \n",
    "\n",
    "        lon=len(jobDifficulty)\n",
    "        if lon<d:\n",
    "            return -1\n",
    "        b={}\n",
    "        for i in range(lon):\n",
    "            q=jobDifficulty[i]\n",
    "            b[i]={}\n",
    "            for j in range(i+1,lon):\n",
    "                b[i][j-1]=q\n",
    "                q=max(q,jobDifficulty[j])\n",
    "            b[i][lon-1]=q\n",
    "        # print(lon)\n",
    "        # print(b)\n",
    "        \n",
    "        a={0:[jobDifficulty[0]]}\n",
    "\n",
    "        for i in range(1,lon):\n",
    "            a[i]=[b[0][i]]\n",
    "            \n",
    "            for j in range(1,min(i+1,d)):\n",
    "                q=a[j-1][j-1]+b[j-1][i]\n",
    "                for k in range(i-j+1):\n",
    "                    q=min(q,a[j-1+k][j-1]+b[j+k][i])\n",
    "                a[i].append(q)\n",
    "                # print(a)\n",
    "        # print(a)\n",
    "        return a[lon-1][d-1]\n",
    "\n",
    "\n",
    "        # global lon,m,a,b\n",
    "        \n",
    "        # a={}\n",
    "        # lon=len(jobDifficulty)\n",
    "        \n",
    "        # if lon<d:\n",
    "        #     return -1\n",
    "        # b={}\n",
    "        # for i in range(lon):\n",
    "        #     q=0\n",
    "        #     b[i]={}\n",
    "        #     for j in range(i,lon):\n",
    "        #         b[i][j]=q\n",
    "        #         q=max(q,jobDifficulty[j])\n",
    "        #     b[i][lon]=q\n",
    "        # # print(b)\n",
    "        \n",
    "        # m=sum(jobDifficulty)\n",
    "        # def fun(n,cal,k,t):\n",
    "        #     global lon,m,a\n",
    "            \n",
    "        #     # print(n,cal,k,a)\n",
    "        #     if n == lon:\n",
    "        #         m=min(m,cal)\n",
    "        #         for i in range(d):\n",
    "\n",
    "\n",
    "        #         return\n",
    "        #     if cal>=m:\n",
    "        #         return \n",
    "        #     if n not in a:\n",
    "        #         a[n]=[cal,k]\n",
    "        #     else:\n",
    "        #         if a[n][1]==k:\n",
    "        #             if a[n][0]<=cal:\n",
    "        #                 return \n",
    "        #             else:\n",
    "        #                 a[n][0]=cal\n",
    "        #         elif a[n][1]>k:\n",
    "        #             if a[n][0]<=cal:\n",
    "        #                 return \n",
    "                    \n",
    "        #     if k<d-1:\n",
    "        #         for i in range(lon-n-(d-k)+1):\n",
    "        #             q=b[n][n+i+1]\n",
    "        #             fun(n+i+1,cal+q,k+1,t+[n+i+1])\n",
    "        #     else:\n",
    "        #         q=b[n][lon]\n",
    "        #         fun(lon,cal+q,k+1,t+[lon])\n",
    "        # fun(0,0,0,[])\n",
    "        # return m\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n=len(jobDifficulty)\n",
    "        dp=[]\n",
    "        for i in range(n):\n",
    "            dp.append([])\n",
    "            temp_max=jobDifficulty[i]\n",
    "            for j in range(i,n):\n",
    "                temp_max=max(temp_max,jobDifficulty[j])\n",
    "                dp[-1].append(temp_max)\n",
    "        @functools.cache\n",
    "        def f_dp(start,cut):\n",
    "            if cut==0: return dp[start][n-1-start]\n",
    "            temp_min=math.inf\n",
    "            for i in range(start,n-cut):\n",
    "                temp_min=min(temp_min,dp[start][i-start]+f_dp(i+1,cut-1))\n",
    "            return temp_min\n",
    "        ans=f_dp(0,d-1)\n",
    "        return-1 if ans==math.inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n = len(jobDifficulty)\n",
    "        if n < d:\n",
    "            return -1\n",
    "        if n == d:\n",
    "            return sum(jobDifficulty)\n",
    "        diff = []\n",
    "        for i in range(n):\n",
    "            temp = [0] * (i+1)\n",
    "            cur = jobDifficulty[i]\n",
    "            for j in range(i, -1, -1):\n",
    "                cur = max(cur, jobDifficulty[j])\n",
    "                temp[j] = cur\n",
    "            diff.append(temp)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, cnt: int):\n",
    "            if cnt == 1:\n",
    "                return diff[n-1][i]\n",
    "            if n-i == cnt:\n",
    "                return sum(jobDifficulty[i:])\n",
    "            ans = inf\n",
    "            for j in range(i, n-cnt+1):\n",
    "                ans = min(ans, diff[j][i] + dfs(j+1, cnt-1))\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, d)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n = len(jobDifficulty)\n",
    "        if d > n: return -1\n",
    "\n",
    "        max_val = [[0] * n for _ in range(n)]\n",
    "        for i, v in enumerate(jobDifficulty):\n",
    "            max_val[i][i] = v\n",
    "        for width in range(2, n+1):\n",
    "            for left in range(n - width + 1):\n",
    "                right = left + width - 1\n",
    "                max_val[left][right] = max(max_val[left][left], max_val[left+1][right])\n",
    "        \n",
    "        record = [[None] * n for _ in range(d+1)]\n",
    "        def dfs(ngroup: int, last: int):\n",
    "            if ngroup == 1:\n",
    "                return max_val[0][last]\n",
    "            \n",
    "            if record[ngroup][last] == None:\n",
    "                ans = float('inf')\n",
    "                for first in range(last, ngroup-2, -1):\n",
    "                    ans = min(ans, dfs(ngroup-1, first-1) + max_val[first][last])\n",
    "                record[ngroup][last] = ans\n",
    "            return record[ngroup][last]\n",
    "        return dfs(d, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, J: List[int], d: int) -> int:\n",
    "        n = len(J)\n",
    "        if n < d: return -1\n",
    "        seg=[[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            mx=J[i]\n",
    "            for j in range(i,n):\n",
    "                mx=max(mx,J[j])\n",
    "                seg[i][j]=mx\n",
    "        @cache\n",
    "        def dp(i,j,k):\n",
    "            if k == 1:\n",
    "                return seg[i][j]\n",
    "            ans = float(\"inf\")\n",
    "            for p in range(i,j-k+2):\n",
    "                ans=min(ans,seg[i][p]+dp(p+1,j,k-1))\n",
    "            return ans\n",
    "        return dp(0,n-1,d)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.m1 = {}\n",
    "\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        \"\"\"\n",
    "        jobDifficulty = [6,5,4,3,2,1], d = 2\n",
    "        :param jobDifficulty:\n",
    "        :param d:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        len1 = len(jobDifficulty)\n",
    "        if d  > len1:\n",
    "            return -1\n",
    "        if d == len1:\n",
    "            return sum(jobDifficulty)\n",
    "        res = self.getN(jobDifficulty, d)\n",
    "        return res\n",
    "\n",
    "\n",
    "    def getN(self, lines, d):\n",
    "        if (tuple(lines), d) in self.m1:\n",
    "            return self.m1[(tuple(lines), d) ]\n",
    "\n",
    "        v1 = math.inf\n",
    "        if d == 1:\n",
    "            res = max(lines)\n",
    "            self.m1[(tuple(lines), d)] = res\n",
    "            return res\n",
    "        for i in range(1, len(lines) - d + 2 ):\n",
    "            left = lines[:i]\n",
    "            right = lines[i:]\n",
    "            cnt1 = max(left)\n",
    "            cnt2 = self.getN(right, d-1)\n",
    "            v1 = min(v1, cnt1 + cnt2)\n",
    "        self.m1[(tuple(lines), d)] = v1\n",
    "        return v1\n",
    "\n",
    "a = Solution()\n",
    "print(a.minDifficulty(jobDifficulty = [6,5,4,3,2,1], d = 2 ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "\n",
    "        # 动态规划，怎么划分，使得整个工作计划难度最小\n",
    "        n = len(jobDifficulty)\n",
    "        preMax = [[0]*n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            x = 0\n",
    "            for j in range(i, n):\n",
    "                x = max(x, jobDifficulty[j])\n",
    "                preMax[i][j] = x \n",
    "        @cache\n",
    "        def dfs(i, tot):\n",
    "            if i == n and tot == 0:\n",
    "                return 0\n",
    "            if (i == n and tot > 0) or (tot == 0):\n",
    "                return inf \n",
    "            res = inf\n",
    "            for j in range(i, n):\n",
    "                res = min(res, preMax[i][j] + dfs(j+1, tot-1))\n",
    "            return res \n",
    "        res = dfs(0, d)\n",
    "        return -1 if res == inf else res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n=len(jobDifficulty)\n",
    "        large=[[0]*n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            q=deque()\n",
    "            for j in range(i,n):\n",
    "                while q and jobDifficulty[j]>q[-1]:\n",
    "                        q.pop()\n",
    "                q.append(jobDifficulty[j])\n",
    "                large[i][j]=q[0]\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j==-1:\n",
    "                if i==0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return inf\n",
    "            if i==0:\n",
    "                return large[i][j]\n",
    "            res=inf\n",
    "            for l in range(i,j+1):\n",
    "                res=min(res,dfs(i-1,l-1)+large[l][j])\n",
    "            return res\n",
    "        ans=dfs(d-1,n-1)\n",
    "        if ans==inf:\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        inf = 10**9\n",
    "        n = len(jobDifficulty)\n",
    "        if d > n: return -1\n",
    "        prem = [0]\n",
    "        for i in range(n):\n",
    "            prem.append(max(prem[i], jobDifficulty[i]))\n",
    "        segmax = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if j == i:\n",
    "                    segmax[i][j] = jobDifficulty[i]\n",
    "                else:\n",
    "                    segmax[i][j] = max(segmax[i][j - 1], jobDifficulty[j])\n",
    "        @cache\n",
    "        def dfs(tpre:int, td:int)->int:\n",
    "            if td > tpre: return inf\n",
    "            if td == 1: \n",
    "\n",
    "                return prem[tpre]\n",
    "            ret = inf\n",
    "            for i in range(1, tpre + 1):\n",
    "                ret = min(ret, dfs(tpre - i, td - 1) + segmax[tpre - i][tpre - 1])\n",
    "            return ret\n",
    "        return dfs(n,d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "#         n = len(jobDifficulty)\n",
    "#         if n < d:\n",
    "#             return -1\n",
    "#         dp = [0] * n\n",
    "#         curMax = jobDifficulty[0]\n",
    "#         for i in range(n):\n",
    "#             curMax = max(curMax, jobDifficulty[i])\n",
    "#             dp[i] = curMax\n",
    "#         for t in range(1, d):\n",
    "#             tmp = [inf] * n\n",
    "#             for j in range(t, n):\n",
    "#                 curMax = jobDifficulty[j]\n",
    "#                 for k in range(j, t - 1, -1):\n",
    "#                     curMax = max(curMax, jobDifficulty[k])\n",
    "#                     tmp[j] = min(tmp[j], dp[k - 1] + curMax)\n",
    "\n",
    "#             dp = tmp\n",
    "#         return dp[-1]\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, job: List[int], d: int) -> int:\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if j == 1:\n",
    "                return g[0][i - 1]\n",
    "\n",
    "            ans = float('inf')\n",
    "            for k in range(1, i - j + 2):\n",
    "                ans = min(ans, f(i - k, j - 1) + g[i - k][i - 1])\n",
    "            return ans\n",
    "\n",
    "        n = len(job)\n",
    "        if n < d: return -1\n",
    "        g = [[-1] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                g[i][j] = max(g[i][j - 1], job[j])\n",
    "        return f(n, d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(start, remain_d):\n",
    "            if remain_d == 1:  # base case\n",
    "                return dp[start][-1]\n",
    "            return min(dp[start][i] + dfs(i + 1, remain_d - 1) for i in range(start, n - remain_d + 1))\n",
    "        \n",
    "        n = len(jobDifficulty)\n",
    "        if n < d:  # edge case\n",
    "            return -1\n",
    "        dp = [[float('inf')] * n for _ in range(n)]  # pre-process: dp[i][j] = min(dp[i:j+1])\n",
    "        for i in range(n):\n",
    "            dp[i][i] = jobDifficulty[i]\n",
    "            for j in range(i + 1, n):\n",
    "                dp[i][j] = max(dp[i][j - 1], jobDifficulty[j])\n",
    "        return dfs(0, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from functools import cache\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class MaxHeap:\n",
    "    def __init__(self, arr: list):\n",
    "        self.heap = [-x for x in arr]\n",
    "        heapq.heapify(self.heap)\n",
    "\n",
    "    def push(self, x):  # 插入元素\n",
    "        heapq.heappush(self.heap, -x)\n",
    "\n",
    "    def pop(self):  # 弹出最大值\n",
    "        return -heapq.heappop(self.heap)\n",
    "\n",
    "    def top(self):  # 返回最大值\n",
    "        return -self.heap[0]\n",
    "\n",
    "\n",
    "class RMinQ:\n",
    "    def __init__(self, arr: list):\n",
    "        self.arr = arr\n",
    "        self.n = len(arr)\n",
    "        self.log = [0] * (self.n + 1)\n",
    "        self.st = [[0] * self.n for _ in range(self.n)]\n",
    "        for i in range(2, self.n + 1):\n",
    "            self.log[i] = self.log[i // 2] + 1\n",
    "        for i in range(self.n):\n",
    "            self.st[i][0] = arr[i]\n",
    "        for j in range(1, self.log[self.n] + 1):\n",
    "            for i in range(self.n - (1 << j) + 1):\n",
    "                self.st[i][j] = min(\n",
    "                    self.st[i][j - 1], self.st[i + (1 << (j - 1))][j - 1]\n",
    "                )\n",
    "\n",
    "    def query(self, l: int, r: int) -> int:\n",
    "        # 闭区间\n",
    "        s = self.log[r - l + 1]\n",
    "        return min(self.st[l][s], self.st[r - (1 << s) + 1][s])\n",
    "\n",
    "\n",
    "class RMaxQ:\n",
    "    def __init__(self, arr: list):\n",
    "        self.arr = arr\n",
    "        self.n = len(arr)\n",
    "        self.log = [0] * (self.n + 1)\n",
    "        self.st = [[0] * self.n for _ in range(self.n)]\n",
    "        for i in range(2, self.n + 1):\n",
    "            self.log[i] = self.log[i // 2] + 1\n",
    "        for i in range(self.n):\n",
    "            self.st[i][0] = arr[i]\n",
    "        for j in range(1, self.log[self.n] + 1):\n",
    "            for i in range(self.n - (1 << j) + 1):\n",
    "                self.st[i][j] = max(\n",
    "                    self.st[i][j - 1], self.st[i + (1 << (j - 1))][j - 1]\n",
    "                )\n",
    "\n",
    "    def query(self, l: int, r: int) -> int:\n",
    "        # 闭区间\n",
    "        s = self.log[r - l + 1]\n",
    "        return max(self.st[l][s], self.st[r - (1 << s) + 1][s])\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n = len(jobDifficulty)\n",
    "\n",
    "        rmq = RMaxQ(jobDifficulty)\n",
    "\n",
    "        # 前 i 个， 干 j 天 的答案\n",
    "        @cache\n",
    "        def f(i: int, j: int) -> int | float:\n",
    "            if j == 0:\n",
    "                if i > 0:\n",
    "                    return float(\"inf\")\n",
    "                return 0\n",
    "            if j > i:\n",
    "                return float(\"inf\")\n",
    "            return min(f(k, j - 1) + rmq.query(k, i - 1) for k in range(i))\n",
    "\n",
    "        ans = f(n, d)\n",
    "        return ans if ans != float(\"inf\") else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n = len(jobDifficulty)\n",
    "        if d > n:\n",
    "            return -1\n",
    "        pre = [[0] * n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            t = 0\n",
    "            for j in range(i, n):\n",
    "                t = max(t, jobDifficulty[j])\n",
    "                pre[i][j] = t \n",
    "        @cache\n",
    "        def dfs(i, k):\n",
    "            \"\"\"\n",
    "            i: 第i个任务\n",
    "            k: 第k天\n",
    "            \"\"\"\n",
    "            if k == 0:\n",
    "                if i == n:\n",
    "                    return 0\n",
    "                if i < n:\n",
    "                    return inf \n",
    "            res = inf\n",
    "            for j in range(i, n):\n",
    "                res = min(res, dfs(j+1, k-1) + pre[i][j])\n",
    "            return res \n",
    "\n",
    "        return dfs(0, d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        n = len(jobDifficulty)\n",
    "        if n < d:\n",
    "            return -1\n",
    "        map = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                map[i][j] = max(jobDifficulty[i:j + 1])\n",
    "\n",
    "        trace = [[-1] * d for _ in range(n)]\n",
    "        def dfs(st: int, m: int, n:int) -> int:\n",
    "            nonlocal map\n",
    "            nonlocal trace\n",
    "            if m == 0:\n",
    "                return map[st][n - 1]\n",
    "            if trace[st][m] != -1:\n",
    "                return trace[st][m]\n",
    "            tmp = 10000\n",
    "            for i in range(st + 1, n - m + 1):\n",
    "                tmp = min(tmp, map[st][i - 1] + dfs(i, m - 1, n))\n",
    "            trace[st][m] = tmp\n",
    "            return tmp\n",
    "        return dfs(0, d - 1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:\n",
    "        \n",
    "        n = len(jobDifficulty)\n",
    "        if n < d:\n",
    "            return -1\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, day, cnt):\n",
    "            if i == n:\n",
    "                if day == 1 and cnt!=-1:\n",
    "                    return cnt\n",
    "                return inf\n",
    "            x = jobDifficulty[i]\n",
    "            res = dfs(i+1, day, cnt if cnt > x else x)\n",
    "            if day > 1 and cnt != -1:\n",
    "                cur = cnt + dfs(i+1, day-1, x)\n",
    "                if cur < res:\n",
    "                    res = cur\n",
    "            return res\n",
    "        return dfs(0, d, -1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
